package com.feishi.project.move;

import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: caixq
 * Date: 2020-01-03
 * Time: 下午12:19
 */
public class TestA {
    public static void main(String[] args) {
        Character c='a';
        ListNode head=new ListNode(1);
        head.next=new ListNode(2);
        head.next.next=new ListNode(3);
        head.next.next.next=new ListNode(4);
        head.next.next.next.next=new ListNode(5);
//        head.next.next.next.next.next=new ListNode(6);
        int[] ints=new int[]{5,1,1};
        nextPermutation(ints);
//        System.out.println(Arrays.deepToString(fillSudoku(new char[][]{
//                new char[]{'.','.','.','.','3','.','.','.','5'},
//                new char[]{'8','.','5','.','2','9','.','.','.'},
//                new char[]{'.','.','.','.','.','.','.','9','8'},
//                new char[]{'.','.','2','5','.','.','4','.','.'},
//                new char[]{'6','.','.','.','.','.','.','.','1'},
//                new char[]{'.','.','9','.','.','7','6','.','.'},
//                new char[]{'4','2','.','.','.','.','.','.','.'},
//                new char[]{'.','.','.','8','1','.','2','.','4'},
//                new char[]{'1','.','.','.','6','.','.','.','.'}
//
//        })));
//        System.out.println(fillSudoku(new String[]{
//                "009748000",
//                "700000000",
//                "020109000",
//                "007000240",
//                "064010590",
//                "098000300",
//                "000803020",
//                "000000006",
//                "000275900"
//
//        }));
        int[][] intervals=new int[][]{
                new int[]{1,3},
                new int[]{6,9}
        };
        int[] newInterval=new int[]{2,5};
        System.out.println(Arrays.deepToString(insert(intervals,newInterval)));

    }
    /**
     * 给出一个无重叠的 ，按照区间起始端点排序的区间列表。
     *
     * 在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
     * */
    public static int[][] insert(int[][] intervals, int[] newInterval) {

        if(intervals.length==0)return new int[][]{newInterval};
        int sIndex= getIndex(intervals,newInterval[0]);
        int eIndex= getIndex(intervals,newInterval[0]);
        List<int[]> result=new ArrayList<>();
        for (int i = 0; i < intervals.length; i++) {
            if(i<sIndex>>1||i>eIndex>>1){
                result.add(intervals[i]);
                continue;
            }
            result.add(new int[]{
                   Math.min(intervals[sIndex>>1][0],newInterval[0]),
                    Math.max(intervals[eIndex>>1][1],newInterval[1])
            });
            i=eIndex>>1;
        }
        return result.toArray(new int[0][]);
    }

    private static int getIndex(int[][] vs, int v) {
        int start=0,length=vs.length,end=length*2-1;
        if(v<=vs[0][0])return 0;
        if(v>=vs[end>>1][1])return end;
        while (start<end-1){
            int mid=(start+end)>>1;
            if(vs[mid>>1][mid&1]==v)return mid;
            if(vs[mid>>1][mid&1]>v)end=mid;
            else start=mid;
        }
        return end;
    }

    /**
     * 给出一个区间的集合，请合并所有重叠的区间。
     * */
    public int[][] merge(int[][] intervals) {
        if(intervals.length==0)return intervals;
        Arrays.sort(intervals, (a, b) -> a[0]-b[0]);
        int[] pre=intervals[0];
        int index=0;
        for (int i = 1; i < intervals.length; i++) {
            if(pre[1]>=intervals[i][0]){
                pre[1]=Math.max(pre[1],intervals[i][1]);
            }else {
                pre=intervals[i];
                index++;
                intervals[index]=pre;
            }
        }
        int[][] out=new int[index+1][];
        System.arraycopy(intervals,0,out,0,out.length);
        return out;
    }

    /**
     * 给定一个非负整数数组，你最初位于数组的第一个位置。
     *
     * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
     *
     * 判断你是否能够到达最后一个位置。
     * */
    public boolean canJump(int[] nums) {
        if(nums.length<2)return true;
        if(nums[0]==0)return false;
        for (int i = 1  ; i < nums.length; i++) {
            nums[i]=Math.max(nums[i-1]-1,nums[i]);
            if(nums[i]==0){
                return i==nums.length-1;
            }
        }
        return true;
    }
    /**
     * 给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。
     * */
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result=new ArrayList<>();
        int arr=0;
        if(matrix.length==0||matrix[0].length==0)return result;
        int m=matrix.length;
        int n=matrix[0].length;
        int x=0,y=0;
        boolean[][] flag=new boolean[m][n];
        flag[0][0]=true;
        result.add(matrix[0][0]);
        while ((arr=hasNext(flag,x,y,arr))!=-1){
            x+= (arr&1)*(((arr&2)==0)?1:-1);
            y+=(((arr&1)==0?1:0)*(((arr&2)==0)?1:-1));

            System.out.println(arr+"::"+x+"::"+y);
            System.out.println(Arrays.deepToString(flag));
            flag[x][y]=true;
            result.add(matrix[x][y]);
        }
        return result;
    }

    private int hasNext(boolean[][] flag, int x, int y, int arr) {
        for (int i = 0; i < 4; i++) {
            boolean f=true;
            switch (arr){
                case 0:
                    if(y+1<flag[0].length)f= flag[x][y+1];break;
                case 1:
                    if(x+1<flag.length) f= flag[x+1][y];break;
                case 2:
                    if(y>0) f= flag[x][y-1];break;
                case 3:
                    if(x>0) f= flag[x-1][y];break;
            }

            if(!f){
                return arr;
            }else {arr=(arr+1)&3;}
        }

        return -1;
    }

    public static int maxSubArray(int[] nums) {
        if(nums.length==0)return Integer.MIN_VALUE;
        int max=nums[0];
        for (int i = 1; i < nums.length; i++) {
            nums[i]=Math.max(nums[i],nums[i-1]+nums[i]);
            max=Math.max(nums[i],max);
        }
        return max;
    }
    public int totalNQueens(int n) {
        AtomicInteger a= new AtomicInteger(1);
        new Thread(()->{
            a.getAndIncrement();
        });
        return solveNQueens(n).size();
    }
    /**
     * n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
     * */
    public static List<List<String>> solveNQueens(int n) {
        int[] indexes=new int[n];
        List<List<String>> result=new ArrayList<>();
        solveNQueens(0,indexes,result);
        return result;
    }

    private static void solveNQueens(int i, int[] indexes, List<List<String>> result) {
        boolean[] bd=new boolean[indexes.length];
        for (int j = 0; j <i ; j++) {
            int a=indexes[j]-i+j;
            int b=indexes[j];
            int c=indexes[j]+i-j;
            if(a>=0) bd[a]=true;
            bd[b]=true;
            if(c<bd.length) bd[c]=true;
        }
        System.out.println(Arrays.toString(indexes));
        System.out.println(Arrays.toString(bd));
        if(i<indexes.length-1){

            for (int j = 0; j <bd.length; j++) {
                if(!bd[j]){
                    indexes[i]=j;
                    solveNQueens(i+1,indexes,result);
                }
            }
        }else {
            for (int j = 0; j < bd.length; j++) {
                if(!bd[j]){
                    indexes[i]=j;
                    System.out.println(">>>>>>>>"+Arrays.toString(indexes));
                    List<String> list=new ArrayList<>();
                    char[] chars=new char[bd.length];
                    for (int k = 0; k < chars.length; k++) {
                        chars[k]='.';
                    }
                    char[] chars1=new char[bd.length];
                    for (int k = 0; k < indexes.length; k++) {
                        System.arraycopy(chars,0,chars1,0,chars.length);
                        chars1[indexes[k]]='Q';
                        list.add(String.valueOf(chars1));
                    }
                    result.add(list);
                }
            }
        }


    }

    public static double myPow(double x, int n) {
        if(x==0)return 0;
        double o=1;
        int index=0;
        if(n==Integer.MIN_VALUE){
            x=1/x;
            while (index<31){
                x*=x;
                index++;
            }
            return x;
        }
        if(n<0){
            x=1/x;
            n=-n;
        }
        while (index<31&&1<<index<=n){
            if((n&(1<<index))!=0){
                o*=x;
            }
            x*=x;
            index++;
        }
        return o;
    }
    /**
     * 给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
     * */
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> result=new ArrayList<>();
        Map<String,List<String>> map=new HashMap<>(strs.length);
        for (String str : strs) {
            char[] cs=str.toCharArray();
            Arrays.sort(cs);
            String st = String.valueOf(cs);
            List<String> list=map.getOrDefault(st,new ArrayList<>());
            list.add(str);

            map.put(st,list);
        }
        result.addAll(map.values());
        return result;
    }
    /**
     * 给定一个 n × n 的二维矩阵表示一个图像。
     *
     * 将图像顺时针旋转 90 度。
     * */
    public void rotate(int[][] matrix) {
        int t;
        int n=matrix.length;

        for (int i = 0; i <n-1 ; i++) {
            for (int j = 0; j < i && j< n-i-1; j++) {
                t=matrix[i][j];
                matrix[i][j]=matrix[n-j-1][i];
                matrix[n-j-1][i]=matrix[n-i-1][n-j-1];
                matrix[n-i-1][n-j-1]=matrix[j][n-i-1];
                matrix[j][n-i-1]=t;
            }
        }

    }
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> result=new ArrayList<>();
        if(nums.length==1){
            List<Integer> list=new ArrayList<>();
            list.add(nums[0]);
            result.add(list);
            return result;
        }else {
            int[] next=new int[nums.length-1];
            HashSet<Integer> set=new HashSet<>();

            for (int i = 0; i < nums.length; i++) {
                if(set.contains(nums[i]))continue;
                set.add(nums[i]);
                System.arraycopy(nums,0,next,0,next.length);
                if(i!=next.length){
                    next[i]=nums[next.length];
                }
                for (List<Integer> list : permuteUnique(next)) {
                    list.add(nums[i]);
                    result.add(list);
                }
            }
        }
        return result;
    }
    /**
     * 递归计算全排列
     * */
    public static List<List<Integer>> permute2(int[] nums) {
        List<List<Integer>> result=new ArrayList<>();
        if(nums.length==1){
            List<Integer> list=new ArrayList<>();
            list.add(nums[0]);
            result.add(list);
            return result;
        }else {
            int[] next=new int[nums.length-1];
            for (int i = 0; i < nums.length; i++) {
                System.arraycopy(nums,0,next,0,next.length);
                if(i!=next.length){
                    next[i]=nums[next.length];
                }
                for (List<Integer> list : permute2(next)) {
                    list.add(nums[i]);
                    result.add(list);
                }

            }
        }

        return result;
    }
    /**
     * 给定一个没有重复数字的序列，返回其所有可能的全排列。
     * */
    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result=new ArrayList<>();
        permute(nums,0,result);
        return result;
    }

    private static void permute(int[] nums, int index,  List<List<Integer>> result) {
        if(index<nums.length-1){
            int[] bak=new int[nums.length-index];
            System.arraycopy(nums,index,bak,0,bak.length);
            for (int i = index; i < nums.length; i++) {
                System.arraycopy(bak,0,nums,index,bak.length);
                exchange(nums,index,i);
                permute(nums, index+1,  result);
            }
        }else {
            List<Integer> list=new ArrayList<>();
            for (int num : nums) {
                list.add(num);
            }
            result.add(list);
            System.out.println(result);
        }
    }

    private static void exchange(int[] nums, int a, int b) {
        int t=nums[a];
        nums[a]=nums[b];
        nums[b]=t;
    }

    private static <T>  void exchange(T[] nums, int a, int b) {
        T t=nums[a];
        nums[a]=nums[b];
        nums[b]=t;
    }
    /**
     * 给定一个非负整数数组，你最初位于数组的第一个位置。
     *
     * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
     *
     * 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
     *
     * */
    public static int jump(int[] nums) {
        int count=0;
        int length=nums.length;
        if(length==0||length==1)return count;
        int index=0;
        int cv;
        count++;
        while (index+nums[index]+1<length){
            cv=nums[index];
            int max=0;
            int nextIndex=0;
            for (int i = 1; i <= cv; i++) {
                int v=nums[index+i]-cv+i;
                if(v>max){
                    max=v;
                    nextIndex=index+i;
                }
            }
            index=nextIndex;
            count++;
        }
        return count;
    }
    /**
     * 给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。
     * */
    public static boolean isMatch2(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int j = 0; j < n ; j++) {
            if (p.charAt(j) == '*') {
                dp[0][j+1] = dp[0][j];
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (s.charAt(i ) == p.charAt(j ) || p.charAt(j ) == '?') {
                    dp[i+1][j+1] = dp[i ][j];
                } else if (p.charAt(j) == '*') {
                    dp[i+1][j+1] = dp[i+1][j ] || dp[i ][j+1];
                }
            }

            for (int j = 0; j < s.length(); j++) {
                System.out.println(Arrays.toString(dp[i]));
            }
            System.out.println("\n\n");
        }
        return dp[m][n];
    }
    public static String multiply(String num1, String num2) {
        if("0".equals(num1)||"0".equals(num2)){
            return "0";
        }
        Map<Integer,Integer> map=new HashMap<>();
        int l=num1.length()+num2.length()-2;
        int x,y;
        for (int i = num1.length()-1; i >=0 ; i--) {
            x=num1.charAt(i)-'0';
            for (int j = num2.length()-1; j >=0 ; j--) {
                y=num2.charAt(j)-'0';
                map.put(l-i-j,map.getOrDefault(l-i-j,0)+x*y);
            }
        }
        StringBuffer sb=new StringBuffer();
        int size=map.size();
        int v=0;
        for (int i = 0; i < size; i++) {
            v+=map.get(i);
            sb.insert(0,v%10);
            v/=10;
        }
        if(v!=0){
            sb.insert(0,v);
        }
        return sb.toString();
    }
    /**
     * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
     * */
    public static int trap(int[] height) {
        if(height.length<3)return 0;
        int result=0;
        int a=0,b=0;
        int length=height.length;

        int max=0;
        int index=getMaxValueIndex(height,0,height.length-1);
        b=index;
        a=index;

        while (a!=0){
            a=getMaxValueIndex(height,0,b-1);

            for (int i = a+1; i < b; i++) {
                result+=height[a]-height[i];
            }
            b=a;
        }
        b=getMaxValueIndex(height,0,index);
        a=index;
        while (b!=length-1){
            b=getMaxValueIndex(height,a+1,length-1);

            for (int i = a+1; i < b; i++) {
                result+=height[b]-height[i];
            }
            a=b;
        }
        return result;
    }

    private static int getMaxValueIndex(int[] height, int start, int end) {
        int max=Integer.MIN_VALUE;
        int index=-1;
        while (start<=end){
            if(max<height[start]){
                index=start;
                max=height[start];
            }start++;
        }

        return index;
    }

    public int firstMissingPositive(int[] nums) {
        Arrays.sort(nums);
        int v=1;
        for (int num : nums) {
            v=v==num?(num+1):v;
        }

        return v;
    }
    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        if (candidates.length==0) return null;
        Arrays.sort(candidates);
        List<List<Integer>> result=new ArrayList<>();
        List<Integer> it=new ArrayList<>();
        combinationSum2(candidates,0,target,it,result);
        return result;
    }
    private static void combinationSum2(int[] candidates, int i, int target, List<Integer> it,List<List<Integer>> result) {
        while (i<candidates.length&&candidates[i]<=target ){
            List<Integer> list = new ArrayList<>();
            list.addAll(it);
            list.add(candidates[i]);
            if(candidates[i]==target){
                result.add(list);
                break;
            }else {

                if(candidates[i]<=target-candidates[i]){
                    combinationSum2(candidates,i+1,target-candidates[i],list,result);
                }
            }

            do{i++;}while (i<candidates.length&&candidates[i]==candidates[i-1]);
        }
    }
    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        if (candidates.length==0) return null;
        Arrays.sort(candidates);
        List<List<Integer>> result=new ArrayList<>();
        List<Integer> it=new ArrayList<>();
        combinationSum(candidates,0,target,it,result);
        return result;
    }

    private static void combinationSum(int[] candidates, int i, int target, List<Integer> it,List<List<Integer>> result) {
        while (i<candidates.length&&candidates[i]<=target ){
            List<Integer> list = new ArrayList<>();
            list.add(candidates[i]);
            list.addAll(it);
            if(candidates[i]==target){
                result.add(list);
                break;
            }else {
                if(candidates[i]<=target-candidates[i]){
                    combinationSum(candidates,i,target-candidates[i],list,result);
                }
            }
            i++;
        }
    }

    public static String countAndSay(int n) {
        if(n==1)
            return "1";
        else {
            String str=countAndSay(n-1);
            System.out.println(str);
            int length=str.length();
            StringBuffer sb=new StringBuffer();
            int i = 0;
            char pc=' ';
            char c;
            int num=0;
            while (i<length){
                c=str.charAt(i);
                if(c==pc){
                    num++;
                }else {
                    if(num>0)sb.append(num).append(pc);
                    pc=c;
                    num=1;
                }
                i++;
            }
            sb.append(num).append(pc);
            return sb.toString();
        }
    }
    /**
     * 解数独
     * */
    private static int fillSudoku(String[] strings) {
        char[][] chars=new char[strings.length][];
        for (int i = 0; i < strings.length; i++) {
            chars[i]=strings[i].replace('0','.').toCharArray();
        }
        return fillSudoku(chars);
    }

    public static int fillSudoku(char[][] chars){

        char[][] board=new char[chars.length][];
        for (int i = 0; i < chars.length; i++) {
            board[i]=new char[chars[i].length];
            for (int j = 0; j < chars[i].length; j++) {
                board[i][j]=chars[i][j];
            }
        }



        Set<Character>[][] sets=new HashSet[9][9];

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                HashSet s=new HashSet();
                for (int k = 1; k <= 9; k++) {
                    s.add((char)(k+'0'));
                }
                sets[i][j]=s;
            }
        }
        int l=81;
        while (true){
            int left=0;
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j <board[i].length ; j++) {
                    if(board[i][j]=='.')left++;
                    System.out.print(board[i][j]+"\t");
                }
                System.out.println();
            }
            if(left==0){
                if(isValidSudoku(board)){
                    for (int i = 0; i < 9; i++) {
                        for (int j = 0; j < 9; j++) {
                            chars[i][j]=board[i][j];
                        }
                    }
                    return 0;
                }
                return -1;
            }
            if(left==l){

                for (int i = 0; i < 9; i++) {
                    for (int j = 0; j <board[i].length ; j++) {
                        if(board[i][j]=='.'&&sets[i][j].size()==2){
                            for (Character character : sets[i][j]) {
                                System.out.println(">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>");
                                board[i][j]=character;
                                if(fillSudoku(board)==0){
                                    for (int k = 0; k < 9; k++) {
                                        for (int m = 0; m < 9; m++) {
                                            chars[k][m]=board[k][m];
                                        }
                                    }
                                    return 0;
                                };
                            }
                            board[i][j]='.';
                        }
                    }
                    System.out.println();
                }

            }
            l=left;

            System.out.println("\n---------------------------------------------------------------\n");

            for (int i = 0; i < 81; i++) {
                int x=i/9;
                int y=i%9;
                char v=board[x][y];
                if(v=='.')continue;
                for (int j = 0; j < 9; j++) {
                    if(j!=y){
                        sets[x][j].remove(v);
                        if(sets[x][j].size()==1){
                            board[x][j]=sets[x][j].iterator().next();
                        }
                    }
                    if(j!=x){
                        sets[j][y].remove(v);
                        if(sets[j][y].size()==1){
                            board[j][y]=sets[j][y].iterator().next();
                        }
                    }
                    int a=x/3*3+j/3,b=y/3*3+j%3;
                    if(a!=x||b!=y){
                        sets[a][b].remove(v);
                        if(sets[a][b].size()==1){
                            board[a][b]=sets[a][b].iterator().next();
                        }
                    }
                }
            }
            for (int i = 0; i < 9; i++) {
                Set<Character> set=new HashSet();
                Map<Integer,Set> map=new HashMap<>();
                for (int j = 0; j <9 ; j++) {
                    set.add((char)(j+'1'));
                }
                for (int j = 0; j <9 ; j++) {
                    if(board[i][j]=='.'){
                        map.put(j,sets[i][j]);
                    }else {
                        set.remove(board[i][j]);
                    }
                }

                for (Character character : set) {
                    int index=getOneCharMapIndex(map,character);
                    if(index>-1){
                        board[i][index]=character;
                    }
                }
                set.clear();
                map.clear();
                for (int j = 0; j <9 ; j++) {
                    set.add((char)(j+'1'));
                }
                for (int j = 0; j <9 ; j++) {
                    if(board[j][i]=='.'){
                        map.put(j,sets[j][i]);
                    }else {
                        set.remove(board[j][i]);
                    }
                }
                for (Character character : set) {
                    int index=getOneCharMapIndex(map,character);
                    if(index>-1){
                        board[index][i]=character;
                    }
                }


                set.clear();
                map.clear();
                for (int j = 0; j <9 ; j++) {
                    set.add((char)(j+'1'));
                }
                for (int j = 0; j <9 ; j++) {
                    if(board[i/3*3+j/3][i%3*3+j%3]=='.'){
                        map.put(j,sets[i/3*3+j/3][i%3*3+j%3]);
                    }else {
                        set.remove(board[i/3*3+j/3][i%3*3+j%3]);
                    }
                }
                for (Character character : set) {
                    int index=getOneCharMapIndex(map,character);
                    if(index>-1){
                        board[i/3*3+index/3][i%3*3+index%3]=character;
                    }
                }
            }

        }
    }

    private static int getOneCharMapIndex(Map<Integer, Set> map, Character character) {
        int num=0;
        int index=0;
        for (Map.Entry<Integer, Set> integerSetEntry : map.entrySet()) {
            if(integerSetEntry.getValue().contains(character)){
                num++;
                index=integerSetEntry.getKey();
            }
        }
        if(num==1){
            return index;
        }else {
            return -1;
        }
    }
    public static boolean isValidSudoku1(char[][] board) {
        int[] rows = new int[9];
        int[] cols = new int[9];
        int[] sub = new int[9];

        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                if(board[i][j] == '.'){
                    continue;
                }
                if(!isValid(rows,i,board[i][j]-'0')){
                    return false;
                }
                if(!isValid(cols,j,board[i][j]-'0')){
                    return false;
                }
                int index = i/3*3+j/3;
                if(!isValid(sub,index,board[i][j]-'0')){
                    return false;
                }
            }
        }

        return true;
    }

    public static boolean isValid(int[] nums, int i, int cur){
        if( ((nums[i] >> cur)&1) == 1){
            return false;
        }
        nums[i] = nums[i] | (1<<cur);
        return true;
    }
    public static   boolean isValidSudoku(char[][] board) {

        Set<Character> set1=new HashSet<>();
        Set<Character> set2=new HashSet<>();
        Set<Character> set3=new HashSet<>();
        for (int i = 0; i < 81; i++) {
            if(i%9==0){
                set1.clear();
                set2.clear();
                set3.clear();
            }
            if(set1.contains(board[i/9][i%9])||set2.contains(board[i%9][i/9])||set3.contains(board[i/9/3*3+i%9/3][i/9%3*3+i%3])){
                return false;
            }
            if(board[i/9][i%9]!='.')set1.add(board[i/9][i%9]);
            if(board[i%9][i/9]!='.')set2.add(board[i%9][i/9]);
            if(board[i/9/3*3+i%9/3][i/9%3*3+i%3]!='.')
                set3.add(board[i/9/3*3+i%9/3][i/9%3*3+i%3]);
        }


        return true;
    }
    public int searchInsert(int[] nums, int target) {

        if(nums.length==0)return -1;
        int start=0,end=nums.length-1;
        boolean flag=false;
        int mid;
        int t=-1;
        if(nums[start]<target)return 0;
        if(nums[end]>target)return end+1;
        if(nums[start]==target)t= start;
        if(nums[end]==target)t= end;
        if(t==-1)
            while (start<end-1){
                mid=(end+start)>>1;
                if(nums[mid]==target){
                    t=mid;break;
                }else if(nums[mid]>target){
                    end=mid;
                }else {
                    start=mid;
                }
            }
        return t!=-1?t:(start+1);
    }
    public static int[] searchRange(int[] nums, int target) {
        int[] result=new int[]{-1,-1};
        if(nums.length==0)return result;
        int start=0,end=nums.length-1;
        boolean flag=false;
        int mid;
        int t=-1;

        if(nums[start]==target)t= start;
        if(nums[end]==target)t= end;
        if(t==-1)
        while (start<end-1){
            mid=(end+start)>>1;
            if(nums[mid]==target){
                t=mid;break;
            }else if(nums[mid]>target){
                end=mid;
            }else {
                start=mid;
            }
        }
        if(t==-1)return result;
        int t0=t;
        if(nums[start]!=nums[t]){

            while (start<t0-1){
                mid=(t0+start)>>1;
                if(nums[mid]!=nums[t]){
                    start=mid;
                }else {
                    t0=mid;
                }
            }
            start=t0;
        }t0=t;

        if(nums[end]!=nums[t]){
            while (end>t0+1){
                mid=(t0+end)>>1;
                if(nums[mid]!=nums[t]){
                    end=mid;
                }else {
                    t0=mid;
                }
            }
            end=t0;
        }

        result[0]=start;
        result[1]=end;

        return result;
    }
    public static int search(int[] nums, int target) {
        if(nums.length==0)return -1;
        if(nums.length==1)return nums[0]==target?0:-1;
        int end=nums.length-1;
        int start=0;

        int mid;
        if(nums[start]==target)return start;
        if(nums[end]==target)return end;
        while (start<end){
            if(start==end-1){
                return -1;
            }
            mid=(end+start)>>1;
            if(nums[mid]==target){
                return mid;
            }else if((nums[start]<nums[mid]&&(nums[mid]<target||nums[start]>target))||(nums[mid]<nums[end]&&nums[end]>target&&nums[mid]<target)){
                start=mid;
            }else {
                end=mid;
            }
        }

        return target;
    }
    public static int longestValidParentheses(String s) {
        int left=0,right=0;
        int max=0;
        int l=s.length();
        int pre=0;
        int end=0;
        int num=0;
        while (end<l){
            if(s.charAt(end)=='('){
                left++;
            }else{
                right++;
            }
            if(left==right){
                num=Math.max(num,left);
            }else if(right>left){
                right=0;
                left=0;
            }
            end++;
        }
        end--;
        left=0;right=0;
//        System.out.println(end);
        while (end>=0){
            if(s.charAt(end)=='('){
                left++;
            }else{
                right++;
            }
            if(left==right){
                num=Math.max(num,left);
            }else if(right<left){
                right=0;
                left=0;
            }
            end--;
        }
        return num*2;
    }
    public static void nextPermutation(int[] nums) {
        if(nums.length==1)return;
        int v;
        int i=nums.length-1;
        while (i>=1&&nums[i]<=nums[i-1]){
            i--;
        }
        if(i!=0){
            int start=i-1,end=nums.length-1;
            v=nums[start];
            for (int j = end; j >start ; j--) {
                if(nums[j]>v){
                    nums[start]=nums[j];
                    nums[j]=v;
                    break;
                }
            }
            start=i;
            end=nums.length-1;
            while (start<end){
                v=nums[start];
                nums[start]=nums[end];
                nums[end]=v;
                start++;end--;
            }


        }else {
            int start=0,end=nums.length-1;
            while (start<end){
                v=nums[start];
                nums[start]=nums[end];
                nums[end]=v;
                start++;end--;
            }
        }
    }
    public List<Integer> findSubstringCopy(String s, String[] words) {
        List<Integer> result = new ArrayList<>();
        int n;
        if (null == words || (n =words.length) == 0) {
            return result;
        }
        int m = s.length(), len = words[0].length();
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.put(words[i], map.getOrDefault(words[i], 0) + 1);
        }
        for (int i = 0; i < len; i++) {
            Map<String, Integer> window = new HashMap<>();
            int left = i, right = i;
            while (right < m - len + 1 && left < m - len * n + 1) {
                String tmpRight = s.substring(right, right + len);
                if (!map.containsKey(tmpRight)) {
                    right += len;
                    left = right;
                    window.clear();
                    continue;
                }
                window.put(tmpRight, window.getOrDefault(tmpRight, 0) + 1);
                right += len;
                while (window.get(tmpRight) > map.get(tmpRight)) {
                    String tmpLeft = s.substring(left, left + len);
                    window.put(tmpLeft, window.get(tmpLeft) - 1);
                    if (window.get(tmpLeft) == 0) {
                        window.remove(tmpLeft);
                    }
                    left += len;
                }
                if (right - left == n * len) {
                    result.add(left);
                }
            }
        }
        return result;
    }
    public static List<Integer> findSubstring(String s, String[] words) {
        List<Integer> list=new ArrayList<>();
        if(words.length==0)return list;
        int size=words[0].length();
        char[] cs=s.toCharArray();
        int index=0;
        String tmp;
        int w=0;
        int ll=cs.length-size*words.length+1;
        while (index<ll){
            w=0;
            int i;
            boolean tag=false;
            int start=0;
            while (w<words.length){
                int k;
                boolean flag=false;
                for (k = w; k < words.length; k++) {
                    i=0;
                    while (i<size&&cs[start+index+i]==words[k].charAt(i)){
                        i++;
                    }
                    if(i==size){
                        flag=true;
                        break;
                    }
                }
                if(!flag){
                    break;
                }
                if(w==words.length-1){
                    tag=true;
                }
                tmp=words[w];
                words[w]=words[k];
                words[k]=tmp;
                w++;
                start+=size;

            }
            if(tag){
                list.add(index);
            }
            index++;

        }
        return list;
    }
    public static int divide(int dividend, int divisor) {

        /** 除数为零就返回-1 按照测试样例的要求写的*/
        if (divisor==0)
            return -1;
        if (dividend==0)
            return 0;
        /** -2147483648, -1 这个测试样例的确没想到，结果翻车了*/
        if (dividend==Integer.MIN_VALUE && divisor==-1)
            return Integer.MAX_VALUE;
        /** 符号位的处理参考了大佬的异或处理方法*/
        boolean negetive= (dividend^ divisor)<0;
        /** div_count 是当前divisor_tmp相对于divisor的倍数 */
        int res=0, div_count=1;
        /** 因为值溢出之后边界问题处理太繁琐了，直接将数值转为long省去麻烦 */
        long dividend_tmp= Math.abs((long)dividend);
        long divisor_tmp= Math.abs((long)divisor);

        /** 按标准的二分查找代码模板写的 */
        while (dividend_tmp>= divisor_tmp) {
            dividend_tmp-= divisor_tmp;
            res+= div_count;

            if (dividend_tmp< Math.abs(divisor))
                break;

            /** divisor_tmp无法倍增时，就将其初始化为divisor绝对值，重新开始下一轮倍增*/
            if (dividend_tmp- divisor_tmp< divisor_tmp) {
                divisor_tmp= Math.abs(divisor);
                div_count=1;
                continue;
            }

            /** 不断倍增divisor_tmp直到和dividend_tmp一样大*/
            divisor_tmp+= divisor_tmp;
            div_count+= div_count;
        }
        return negetive? 0-res: res;

    }

    public static int opposite(int x) {
        return ~x + 1;
    }
    public int strStr(String haystack, String needle) {
        char[] hs = haystack.toCharArray();
        char[] ns = needle.toCharArray();
        int index=0;
        for (int i = 0; i < hs.length- ns.length+1; i++) {
            index=0;
            while (hs[i]==ns[index]&&index<ns.length){
                index++;
            }
            if(index==ns.length)return i;
        }


        return -1;
    }
    public int removeElement(int[] nums, int val) {
        int index=0;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]!=val){
                nums[index++]=nums[i];
            }
        }
        return index;
    }
    public int removeDuplicates(int[] nums) {
        if(nums.length==0)return 0;
        int v=nums[0];
        int index=1;
        for (int i = 1; i < nums.length; i++) {
            if(nums[i]==v){
                continue;
            }else {
                v=(nums[index]=nums[i]);
                index++;
            }
        }
        return index;
    }
    public static ListNode reverseKGroup(ListNode head, int k) {
        if(k<2)return head;
        ListNode listNode=head;
        ListNode n=null;
        ListNode p=null;
        ListNode start=null;
        ListNode end;
        int i=0;
        while (listNode!=null){
            if(i==0){
                start=listNode;
            }
            if(i==k-1){
                end=listNode;
                listNode=listNode.next;
                end=reverseNode(start,end);
                if(p!=null)p.next=end;
                if(n==null)n=end;
                i=0;p=start;
                p.next=null;
                continue;
            }
            i++;
            listNode=listNode.next;

        }
        if(i!=0){
            if(p!=null)p.next=start;
            else return start;
        }
        return n;
    }

    private static ListNode reverseNode(ListNode start, ListNode end) {
        ListNode next=start.next;
        ListNode tmp;
        while (start!=end){
            if(next==null){
                return start;
            }
            tmp=next.next;
            next.next=start;
            start=next;
            next=tmp;
        }
        return end;
    }

    public ListNode swapPairs(ListNode head) {
        if(head==null||head.next==null)return head;
        ListNode node=head;
        head=head.next;
        ListNode pre=null;
        while (node!=null&&node.next!=null){
            if(pre!=null){
                pre.next=node.next;
            }
            pre=node.next.next;
            node.next.next = node;
            node.next=pre;
            pre=node;
            node=node.next;
        }
        return head;
    }
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length==0)return null;
        List<Integer> list=new ArrayList<>();
        for (int i = 0; i < lists.length; i++) {
            ListNode node=lists[i];
           while (node!=null){
               list.add(node.val);
               node=node.next;
           }
        }
        Collections.sort(list);
        ListNode node=new ListNode(0);
        ListNode o=node;
        for (Integer integer : list) {
            node.next=new ListNode(integer);
            node=node.next;
        }

        return o.next;
    }

    private ListNode mergeKLists(ListNode out, ListNode list) {
        return null;
    }

    public static List<String> generateParenthesis(int n) {
        List<String> list=new ArrayList<>();
        if(n==1){
            list.add("()");
            return list;
        }
        char[] b=new char[n*2];
        for (int i = 0; i < b.length; i++) {
            b[i]=')';
        }
        generateParenthesis(list,b,0,0);
        return list;
    }

    private static void generateParenthesis(List<String> list, char[] cs, int i,int index) {
        if(i==0){
            cs[0]='(';
            generateParenthesis(list,cs,i+1,index+1);
        }else if(i<cs.length/2-1){
            for (int j = index; j <= i*2 ; j++) {
                if(j!=index)cs[j-1]=')';
                cs[j]='(';
                for (int k = j+1; k < cs.length; k++) {
                    cs[k]=')';
                }
                generateParenthesis(list,cs,i+1,j+1);
            }
        }else if(i==cs.length/2-1){
            for (int j = index; j < cs.length-1 ; j++) {
                if(j!=index)cs[j-1]=')';
                cs[j]='(';
                list.add(new String(cs));
            }
        }
    }

    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null)return l2;
        if(l2==null)return l1;
        ListNode head=null;
        if(l1.val>l2.val){
            head=l2;
            l2=l2.next;
        }else {
            head=l1;
            l1=l1.next;
        }
        ListNode node=head;
        while (l1!=null&&l2!=null){

            if(l1.val>l2.val){
                node.next=l2;
                l2=l2.next;
            }else {
                node.next=l1;
                l1=l1.next;
            }
            node=node.next;
        }
        if(l1!=null)node.next=l1;
        if(l2!=null)node.next=l2;

        return head;
    }
    public static boolean isValid(String s) {
        Map<Character,Character> cm=new HashMap<>();
        cm.put('(',')');
        cm.put('[',']');
        cm.put('{','}');
        int i=0;
        int length=s.length();
        char[] cs=new char[s.length()/2];
        int csi=0;
        char c;
        Character cc=null;
        while (i<length){
            c=s.charAt(i);
            cc=cm.get(c);
            if(cc==null){
                if(csi==0)return false;
                if(cs[csi-1]!=c)return false;
                csi--;
            }else {
                cs[csi]=cc;

                csi++;
                if(csi>=cs.length)return false;
            }
            i++;
        }
        return csi==0;
    }

    private char getChars(String s, int i,char c,String code) {
        if(s.charAt(i)==c);

        return 0;
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode node=head;
        ListNode[] nodes=new ListNode[1];
        removeFromEnd(node,n+1,nodes);
        node=nodes[0];
        if(node.next!=null)node.next=node.next.next;
        return head;
    }

    private int  removeFromEnd(ListNode node, int n,ListNode[] nodes) {
        int deep;
        if(node.next==null){
            deep=1;
        }else {
            deep=removeFromEnd(node.next,n,nodes)+1;
        }
        System.out.println(n);
        if(deep==n){nodes[0]=node;}
        return deep;
    }

    public static List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result=new ArrayList<>();
        if(nums.length<4)return result;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length-3; i++) {
            if(i!=0&&nums[i]==nums[i-1])continue;
            if(nums[i]*4>target)break;
            for (int j = i+1; j < nums.length-2; j++) {
                if(j!=i+1&&nums[j]==nums[j-1])continue;
                if(nums[i]+nums[j]*3>target)break;
                List<List<Integer>> list=findNears(nums,j+1,nums.length-1,target-nums[i]-nums[j]);
                for (List<Integer> integers : list) {
                    List<Integer> list1=new ArrayList<>(4);
                    list1.add(nums[i]);
                    list1.add(nums[j]);
                    list1.addAll(integers);
                    result.add(list1);
                }
            }
        }

        return result;
    }

    private static List<List<Integer>> findNears(int[] nums, int start, int end, int value) {
        List<List<Integer>> list=new ArrayList<>();
        int dif;
        while (start<end){
            dif=value-nums[start]-nums[end];
            if(dif>0){
                start++;
            }else if(dif<0){
                end--;
            }else {
                list.add(Arrays.asList(nums[start],nums[end]));
                do {start++;}while (start<end&&nums[start]==nums[start-1]);
                do {end--;}while (start<end&&nums[end]==nums[end+1]);
            }
        }
        return list;
    }

    public List<String> letterCombinations(String digits) {     if(digits.length()<1) return new ArrayList();
        int[] indexes=new int[digits.length()];
        List<String> list=new ArrayList();
        char[][]cs=new char[][]{
                new char[]{'a','b','c'},
                new char[]{'d','e','f'},
                new char[]{'g','h','i'},
                new char[]{'j','k','l'},
                new char[]{'m','n','o'},
                new char[]{'p','q','r','s'},
                new char[]{'t','u','v'},
                new char[]{'w','x','y','z'},
        };
        matchAll(digits,cs,indexes,0,list);
        return list;
    }
    public void matchAll(String digits,char[][] cs,int[] indexes,int index,List<String> list){
        char[] chars=cs[digits.charAt(index)-'2'];
        if(index==digits.length()-1){
            for(int i=0;i<chars.length;i++){
                char[] cc=new char[indexes.length];
                for(int j=0;j<indexes.length-1;j++){
                    cc[j]=cs[digits.charAt(j)-'2'][indexes[j]];
                }
                cc[cc.length-1]=chars[i];
                list.add(new String(cc));
            }
        }else{
            for(int i=0;i<chars.length;i++){
                indexes[index]=i;
                matchAll(digits,cs,indexes,index+1,list);
            }
        }
    }
    public static int threeSumClosest(int[] nums, int target) {
        if(nums.length<3)return 0;
        Arrays.sort(nums);
        int value=nums[0]+nums[1]+nums[2];
        for (int i = 0; i < nums.length - 2; i++) {
            int a=i+1,b=nums.length-1;
            int v;

            while (a<b){
                v=nums[i]+nums[a]+nums[b]-target;
                if(Math.abs(v)<Math.abs(value-target)){
                    value=target+v;
                }

                if(v<0){
                    a++;
                }else if(v>0){
                    b--;
                }else {
                    return target;
                }
            }
        }
        return value;
    }
    public static List<List<Integer>> threeSum(int[] nums) {
        if(nums.length<3)return new ArrayList<>();
        ArrayList<List<Integer>> out = new ArrayList<>();
        Arrays.sort(nums);
        int a,b;
        for (int i = 0; i < nums.length-2; i++) {
            if(nums[i]>0)break;
            if(i!=0&&nums[i]==nums[i-1]){continue;}
            a=i+1;
            b=nums.length-1;
            int v;
            while (a<b){
                v=nums[i]+nums[a]+nums[b];
                if(v<0){
                    do{a++;}while (a<b&&nums[a-1]==nums[a]);
                }else if(v>0){
                    do{b--;}while (a<b&&nums[b+1]==nums[b]);
                }else {
                    out.add(Arrays.asList(nums[i],nums[a],nums[b]));
                    do{a++;}while (a<b&&nums[a-1]==nums[a]);
                    do{b--;}while (a<b&&nums[b+1]==nums[b]);

                }
//                while (a<b&&nums[a+1]==nums[a])a++;
//                while (a<b&&nums[b-1]==nums[b])b--;
            }

        }
        return out;
    }


    public static String longestCommonPrefix(String[] strs) {
        if (strs==null||strs.length==0)return null;
        if (strs.length==1)return strs[0];
        char c;
        int i = 0;
        out:for (; i < strs[0].length(); i++) {
            c=strs[0].charAt(i);
            for (int j = 1; j < strs.length; j++) {
                if(strs[j].length()==i||strs[j].charAt(i)!=c)break out;
            }
        }

        return strs[0].substring(0,i);
    }
    public int romanToInt(String s) {
        Map<Character,Integer> vs=new HashMap<>();
        vs.put('I',1);
        vs.put('V',5);
        vs.put('X',10);
        vs.put('L',50);
        vs.put('C',100);
        vs.put('D',500);
        vs.put('M',1000);
        int out=0;
        int pre=0;
        int v;
        for (int i = s.length()-1; i >=0 ; i--) {
            v=vs.get(s.charAt(i));
            if(v>=pre){
                out+=v;
                pre=v;
            }else {
                out-=v;
            }
        }

        return out;
    }
    static char[] cs = new char[]{'I','V','X','L','C','D','M'};
    public static String intToRoman(int num) {
        int index=0;
        int v;
        StringBuffer sb=new StringBuffer();
        while (num>0){
            v=num%10;
            if(v%5==4){
                sb.insert(0,cs[index*2+(v/5==0?1:2)]);
                sb.insert(0,cs[index*2]);
            }else {
                for (int i = 0; i < v%5; i++) {
                    sb.insert(0,cs[index*2]);
                }
                if(v/5==1){
                    sb.insert(0,cs[index*2+1]);
                }
            }
            num/=10;
            index++;
        }
        return sb.toString();
    }
    public static int maxArea(int[] height) {
        int max=0;
        int a=0,b=height.length-1,aa,bb;
        int v;

        while (a!=b){
            aa=height[a];
            bb=height[b];
            int high = aa>bb?aa:bb;
            v=high*(b-a);
            max=max>v?max:v;
            if(aa<bb){
                a++;
            }else {b--;}
        }
        return max;
    }

        public static boolean isPalindrome(int x) {
        if(x<0)return false;
        if(x>10&&x%10==0)return false;
        int v=0;
        while (x>v){
            v=v*10+x%10;
            x/=10;
            System.out.println(v);
            System.out.println(x);
        }

        return x==v||x==v/10;
    }


        public static int myAtoi(String str) {
      long result=0;
      int index=-1;
      int sta=0;
      char c;
      boolean f=true;
      while (index<str.length()-1){
          index++;
          c=str.charAt(index);

          if(sta==0){
              if(c==' ')continue;
              else if(c=='+'){
                  f=true;
              }else if(c=='-'){
                  f=false;
              }else if(c>='0'&&c<='9'){
                  result=c-'0';
              }else {
                  break;
              }

              sta=1;
          }else {
              if(c>='0'&&c<='9'){
                  result=result*10+c-'0';
              }else {
                  break;
              }
              if(result>Integer.MAX_VALUE)break;
          }
      }
        result*=f?1:-1;
      result=result>Integer.MAX_VALUE?Integer.MAX_VALUE:result;
      result=result<Integer.MIN_VALUE?Integer.MIN_VALUE:result;

      return (int) result;
    }

    public static int reverse(int x) {
        long result=x%10;
        x=x/10;
        while (x!=0){
            result=result*10+x%10;
            x=x/10;
        }
        if(result>Integer.MAX_VALUE||result<Integer.MIN_VALUE)return 0;
        return (int) result;
    }
    public static String convert(String s, int numRows) {
        if(numRows==1){
            return s;
        }


        int num=numRows*2-2;
        int length=s.length();
        int w=length/num*2+(length%num==0?0:(length%num>=numRows?2:1));
        char[][] cs=new char[numRows][w];
//        System.out.println(num+"::"+cs[0].length);
        char[] out=new char[s.length()];
        boolean nex;
        for (int i = 0; i < length; i++) {
            nex=(i%num)>=numRows;
            if(!nex){
//                System.out.println(i);
                cs[i%num][i/num*2]=s.charAt(i);
            }else {
                cs[num-i%num][i/num*2+1]=s.charAt(i);
            }
        }
        int n=0;
        int index=0;
        char c;
        while (index<numRows*cs[0].length){
            c=cs[index/w][index%w];
            if(c!=0){
                out[n++]=c;
            }
            index++;
        }
//        System.out.println(Arrays.deepToString(cs));

        return new String(out);
    }
    /*    *
          Definition for singly-linked list.*/
    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }

        @Override
        public String toString() {
            return val+(next==null?"":(":"+next.toString()));
        }
    }
    public static boolean isMatchCopy(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] bp = new boolean[m+1][n+1];
        bp[0][0] = true;
        for(int i = 0; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(p.charAt(j-1) == '*')
                    bp[i][j] = bp[i][j-2] || (i > 0 && bp[i-1][j] &&(p.charAt(j-2) == '.' || s.charAt(i-1) == p.charAt(j-2)));
                else bp[i][j] =i > 0 && bp[i-1][j-1] && (p.charAt(j-1) == '.' || s.charAt(i-1) == p.charAt(j-1));
            }
        }
        return bp[m][n];
    }
    public static boolean isMatch(String s, String p) {

        if(s==null||p==null)return false;
        if(p.length()==0){
            if(s.length()==0){
                return true;
            }return false;
        }
        return isMatch(s,p,0,0);
    }

    public static boolean isMatch(String s, String p, int ss, int ps) {
        if(ss==s.length() && ps==p.length()){
            return true;
        }
        for (int i = ps; i <p.length()-1 ; i++) {

            if(p.charAt(i+1)=='*'){
                if(isMatch(s,p,ss,i+2)){
                    return true;
                }
                if(ss<s.length()){
                    if(p.charAt(i)=='.'){
                        for (int j = ss; j < s.length(); j++) {
                            if(isMatch(s,p,j+1,i+2)){
                                return true;
                            }
                        }
                    }else {
                        for (int j = ss; j < s.length(); j++) {
                            if(s.charAt(j)==p.charAt(i)){
//                            if(s.charAt(j)=='a')
//                            System.out.println(s.charAt(j));
                                if(isMatch(s,p,j+1,i+2)){
                                    return true;
                                }
                            }else{
                                break;
                            }
                        }
                    }
                }
            }
            if(ss<s.length()){
                if(p.charAt(i)=='.'||p.charAt(i)==s.charAt(ss)){
                    ss++;
                }else {
                    return false;
                }
            }else{
                return false;
            }

        }
        if(ss>=s.length())return false;
        if(p.charAt(p.length()-1)!='*'
                &&(p.charAt(p.length()-1)=='.'||p.charAt(p.length()-1)==s.charAt(ss))&&
                ss==s.length()-1){
            return true;
        }
        return false;
    }




    public static String longestPalindrome(String s) {
        if(s.length()==1||s.length()==0)return s;
        int start=0;
        int a,b,st=0,ed=0;

        while (start<s.length()){
            a=start;b=start;
            while (b+1<s.length()&&s.charAt(a)==s.charAt(b+1)){
                b++;
            }
            start=b;
            while (a>=0&&b<s.length()&&s.charAt(a)==s.charAt(b)){
                a--;b++;
            }
            if(b-a>ed-st){
               st=a;ed=b;
            }
            start++;
        }
        System.out.println(st);
        System.out.println(ed);
        return s.substring(st+1,ed);
    }
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int length=nums1.length+nums2.length;
        int i=0,j=0;
        int mIndex=length/2;
        int index=0;
        double c=0;
        while (index++!=mIndex){
            if(i==nums1.length){
                c=nums2[j];j++;continue;
            }
            if(j==nums2.length){
                c=nums1[i];i++;continue;
            }


            if(nums1[i]<nums2[j]){
                c=nums1[i];i++;
            }else {
                c=nums2[j];j++;
            }
        }
        double v=i==nums1.length?nums2[j]:(j==nums2.length?nums1[i]:(nums1[i]<nums2[j])?nums1[i]:nums2[j]);
        if(mIndex*2==length){
            return (c+v)/2;
        }else {
            return v;
        }
    }
    public static int lengthOfLongestSubstring(String s) {
        int length=s.length();
        int start=0;
        int end=0;
        int result=0;
        char c;
        while (end<length){
            c=s.charAt(end);
            for (int i = start; i < end; i++) {
                if(s.charAt(i)==c){
                    result=result>(end-start)?result:(end-start);
                    start=i+1;
                    break;
                }
            }
            end++;
        }

        result=result>(end-start)?result:(end-start);
        return result;
    }

        public int[] twoSum(int[] nums, int target) {
        int length=nums.length;
        Map<Integer,Integer> map=new HashMap<>(nums.length);
        int v;
        Integer j;
        for (int i = 0; i < length; i++) {
            v=target-nums[i];
            j=map.get(nums[i]);
            if(j==null){
                map.put(v,i);
            }else {
                return new int[]{j,i};
            }
        }
        return null;
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int left=0;
        ListNode result=l1;
        l1.val+=l2.val;
        while (l1.next!=null&&l2.next!=null){
            l1=l1.next;
            l2=l2.next;
            l1.val+=l2.val;
        }
        if(l2.next!=null){
            l1.next=l2.next;
        }
        l1=result;
        left=l1.val/10;
        l1.val%=10;
        while (l1.next!=null){
            l1=l1.next;
            l1.val+=left;
            left=l1.val/10;
            l1.val%=10;
        }
        if(left==1){
            l1.next=new ListNode(left);
        }
        return result;
    }
}
